package LeetCode;

public class EditDistance {
  
  //pass both
  //very important
  public static int minDistance(String word1, String word2){
    int m=word1.length();
    int n=word2.length();
    int[][]d=new int[m+1][n+1];
    for(int i=0;i<=m;i++){
      d[i][0]=i;
    }
    for(int j=0;j<=n;j++){
      d[0][j]=j;
    }
    for(int j=1;j<=n;j++){
      for(int i=1;i<=m;i++){
        if(word1.charAt(i-1)==word2.charAt(j-1)){
          d[i][j]=d[i-1][j-1];
        }
        else{
          d[i][j]=min((d[i-1][j]+1),(d[i][j-1]+1),(d[i-1][j-1]+1));
        }
      }
    }
    return(d[m][n]);
  }
  
  public static int min(int a,int b,int c){
    return(Math.min(Math.min(a,b),c));
  }
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub

  }

}
